/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.ArrayList;
import java.util.List;

public class WordOnBoardFinder
{
	/**
	 * Return a list of cells on the given board such that the i-th element of the list corresponds to the i-th character of the string as found on the board. Returns an empty list if the word cannot be found on the board.
	 * 
	 * @param board
	 *            is searched for the given word
	 * @param word
	 *            is being searched for on the board
	 * @return list of cells on the supplied board that correspond to the word, an empty list should be returned if the word cannot be found on the board
	 */
	public List<BoardCell> cellsForWord(BoggleBoard board, String word)
	{
		List<BoardCell> list = new ArrayList<BoardCell>();
		boolean visited [][] = new boolean[board.size()][board.size()];
		
		word = word.toUpperCase(); //put word in upper case
		
		for (int y = 0; y != board.size(); y++)
		{
			for (int x = 0; x != board.size(); x++)
			{
				if (findWord(x, y, 0, word, board, visited, list))
				{
					return list;
				}
			}
		}

		return list;
	}

	/**
	 * Recursive helper function for cellsForWord.
	 * Populates cellList with appropriate BoardCells if word can be found in board.
	 * Returns true when successful.
	 * Does not change the value of word or board.
	 * 
	 * @param x
	 * 		The x location of the board cell being examined.
	 * @param y
	 * 		The y location of the board cell being examined.
	 * @param index
	 * 		The index of the character in word that needs to be matched by board(x, y) in this call.
	 * @param word
	 * 		The string that is trying to be found in board. Should be in upper case.
	 * @param board
	 * 		BoggleBoard object in which word is trying to be found.
	 * @param visited
	 * 		Two-dimensional boolean array the same size as board that is true for cells that have already been visited.
	 * @param cellList
	 * 		The initially empty ArrayList where the BoardCells that form word will be added.
	 * 		When true is returned, this list will contain all the BoardCells necessary for word.
	 * 		When false is returned, this list may be empty or may contain a portion of word.
	 * 
	 * @return Returns true if the entire word was found with no problems. Returns false if word not found.
	 */
	private boolean findWord(int x, int y, int index, String word, BoggleBoard board, boolean [][] visited, List<BoardCell> cellList)
	{
		if (index == word.length())
		{
			return true;
		}
		
		//get character at index of interest
		char c = word.charAt(index); //should already be in upper case since word should be
		
		//if characters at word(index) and board(x, y) match 
		if (c == Character.toUpperCase(board.getFace(x, y).charAt(0))) //ensure character from board is in upper case as well
		{			
			cellList.add(new BoardCell(x, y)); //add board(x, y) to list
			visited[x][y] = true; //mark this cell as visited before recursive calls
			
			//if c was the last character in the word, word has been found so return true
			if (index == word.length() - 1)
			{
				return true;
			}
			
			if (c == 'Q')
			{
				index++; //increase index to account for u after Q
			}
			
			//loop through all board cells bordering (x, y)
			for (int j = -1; j != 2; j++)
			{
				for(int i = -1; i != 2; i++)
				{
					//if cell is not current cell and is in bounds and not already visited
					if ((i != 0 || j != 0) && board.isInBounds(x + i, y + j) && !visited[x + i][y + j])
					{	
						//return true if the part of word after the first character is found in bordering cells
						if (findWord(x + i, y + j, index + 1, word, board, visited, cellList))
						{
							return true;
						}
					}
				}
			}
			
			//if program gets to here, word was not found connected to current cell, so reset changed values
			visited[x][y] = false; //unvisit current cell so potential future calls have clean slate
			cellList.remove(cellList.size() - 1); //remove this cell from list since it's path is incorrect
		}

		return false; //if word was not found after looping through all possibilities, it is not in board
	}
}